UVa/11590 - Prefix lookup/11590.6.cpp

   1 /*
   2   Accepted!
   3  */
   4 #include <iostream>
   5 #include <map>
   6 #include <cstdio>
   7 #include <cstring>
   8 #include <cassert>
   9
  10 using namespace std;
  11
  12 #define D(x) cout << #x " is " << (x) << endl
  13
  14 typedef unsigned long long uint64;
  15
  16 struct node{
  17   bool end;
  18   node * left;
  19   node * right;
  20   node(bool end) : end(end) {
  21     left = right = NULL;
  22   }
  23   node * getLeft(){
  24     if (left == NULL) left = new node(false);
  25     return left;
  26   }
  27   node * getRight(){
  28     if (right == NULL) right = new node(false);
  29     return right;
  30   }
  31 };
  32
  33 //return 2^e
  34 inline uint64 pow2(int e){
  35   if (e == 64) return 0;
  36   return uint64(1) << e;
  37 }
  38
  39 void clean(node * cur){
  40   if (cur == NULL) return;
  41   clean(cur->left);
  42   clean(cur->right);
  43   delete cur;
  44 }
  45
  46 int n, m;
  47
  48 /*
  49   Returns how many strings were counted under the tree rooted at cur, including it.
  50 */
  51 uint64 alreadyCounted(node * cur, int depth = 0){
  52   if (cur == NULL) return 0;
  53   uint64 left = alreadyCounted(cur->left, depth + 1);
  54   uint64 right = alreadyCounted(cur->right, depth + 1);
  55   uint64 ret = left + right;
  56   if (cur->end){
  57     //count strings matched to this one
  58     ret += pow2(m - depth) - left - right;
  59   }
  60   return ret;
  61 }
  62
  63
  64 string buf;
  65 int main(){
  66   while (true){
  67     cin >> n  >> m;
  68     if (n == 0 && m == 0) break;
  69     node * root = new node(true);
  70     for (int i=0; i<n; ++i){
  71       cin >> buf;
  72       node * cur = root;
  73       for (int j=0; ; ++j){
  74         if (buf[j] == '*'){
  75           cur->end = true;
  76           break;
  77         }
  78         node * next;
  79         if (buf[j] == '0'){
  80           next = cur->getLeft();
  81         }else if (buf[j] == '1'){
  82           next = cur->getRight();
  83         }else{
  84           printf("Bad character %c at query %d, position %d\n", buf[j], i, j);
  85           //assert(false);
  86         }
  87         cur = next;
  88       }
  89     }
  90     int k;
  91     cin >> k;
  92     for (int i=0; i<k; ++i){
  93       cin >> buf;
  94       node * cur = root;
  95       for  (int j=0; buf[j] != '*'; ++j){
  96         if (buf[j] == '0'){
  97           cur = cur->left;
  98         }else if (buf[j] == '1'){
  99           cur = cur->right;
 100         }
 101       }
 102       string s = buf.substr(0, buf.size()-1);
 103       uint64 ans = pow2(m - s.size())
 104         - alreadyCounted(cur->left, s.size()+1) - alreadyCounted(cur->right, s.size()+1);
 105       cout << ans << endl;
 106     }
 107     printf("\n");
 108     clean(root);
 109   }
 110   return 0;
 111 }